package lc;

import lc.q51_100.Q56;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
 */
public class Q560 {

    public int subarraySum2(int[] nums, int k) {
        Map<Integer, Integer> counts = new HashMap<>();
        counts.put(0, 1);
        int times = 0;
        int sum = 0;
        for (int num : nums) {
            sum += num;
            int l = sum - k;
            if (counts.get(l) != null) {
                final Integer value = counts.get(l);
                times += value;
            }
            counts.put(sum, counts.getOrDefault(sum,0) + 1);
        }
        return times;
    }

    public int subarraySum(int[] nums, int k) {
        // 先暴力解法
        int[] nums2 = new int[nums.length + 1];
        nums2[0] = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            nums2[i+1] = sum;
        }
        // 现在就是从nums2中寻找和为k的数
        int count  = 0;
        for (int i = 0; i < nums2.length - 1; i++) {
            for (int i1 = i + 1; i1 < nums2.length; i1++) {
                if (nums2[i1] - nums2[i] ==k) {
                    count ++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        final Q560 q560 = new Q560();
        final int i = q560.subarraySum2(new int[]{
                1, 1,1,1
        }, 2);
        System.out.println(i);
    }

}
